#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<stack>
using namespace std;

//class Solution {
//public:
//    int findKthLargest(vector<int>& nums, int k) {
//        int n = nums.size();
//        for (int i = (n - 1 - 1) / 2; i >= 0; i--)
//        {
//            adjustdown(nums, n, i);
//        }
//        for (int i = 0; i < k - 1; i++)
//        {
//            swap(nums[0], nums[n - 1 - i]);
//            adjustdown(nums, n -1 - i, 0);
//        }
//        return nums[0];
//    }
//    void adjustdown(vector<int>& nums, int last, int parent)
//    {
//        int child = parent * 2 + 1;
//        while (child < last)
//        {
//            if (child + 1 < last && nums[child] < nums[child + 1]) child++;
//            if (nums[parent] < nums[child])
//            {
//                swap(nums[parent], nums[child]);
//                parent = child;
//                child = parent * 2 + 1;
//            }
//            else
//                break;
//        }
//    }
//};

class Solution {
public:
    string solve(string s, string t) {
        if (s == "0" || t == "0")
            return "0";
        int n = s.size(), m = t.size();
        if (n == 0 || m == 0)
            return "0";
        string ret(m + n, '0');
        for (int i = n - 1; i >= 0; i--)
        {
            for (int j = m - 1; j >= 0; j--)
            {
                int tmp = (s[i] - '0') * (t[j] - '0');
                tmp += ret[i + j + 1] - '0';
                ret[i + j + 1] = (tmp % 10) + '0';
                ret[i + j] = ret[i + j] + (tmp / 10);
            }
        }
        int i = 0;
        while (i <= m + n - 1 && ret[i] == '0')
            i++;
        return ret.substr(i);
    }
    struct ListNode {
        int val;
        struct ListNode* next;
        ListNode(int x) : val(x), next(nullptr) {}
        
    };
    int findKthLargest(vector<int>& nums, int k) {
        srand(time(NULL));
        return qsort(nums, 0, nums.size() - 1, k);
    }
    int qsort(vector<int>& nums, int l, int r, int k)
    {
        if (l == r)  return nums[l];

        int key = getRandom(nums, l, r);

        int left = l - 1, right = r + 1, i = l;
        while (i < right)
        {
            if (nums[i] < key)   swap(nums[++left], nums[i++]);
            else if (nums[i] == key) ++i;
            else    swap(nums[--right], nums[i]);
        }

        int c = r - right + 1, b = right - left - 1;
        if (c >= k)    return qsort(nums, right, r, k);
        else if (c + b >= k) return key;
        else    return qsort(nums, l, left, k - b - c);
    }

    int getRandom(vector<int>& nums, int left, int right)
    {
        return nums[rand() % (right - left + 1) + left];
    }

    string solve(string s, string t) {
        int n = s.size(), m = t.size();
        int x = max(n, m) + 1;
        string ret(x, 0);

        int flag = 0;
        while (n > 0 || m > 0)
        {
            int a = n == 0 ? 0 : s[n-- - 1] - '0';
            int b = m == 0 ? 0 : t[m-- - 1] - '0';
            int sum = a + b + flag;
            flag = sum / 10;
            sum %= 10;
            ret.insert(ret.begin(), sum + '0');
        }
        if (flag)
            ret.insert(ret.begin(), '1');
        return ret;
    }

    ListNode* addInList(ListNode* head1, ListNode* head2) {
        stack<ListNode*> s1, s2;
        ListNode* cur1 = head1;
        ListNode* cur2 = head2;
        int h1 = 0, h2 = 0;
        while (cur1)
        {
            s1.push(cur1);
            cur1 = cur1->next;
            h1++;
        }
        while (cur2)
        {
            s2.push(cur2);
            cur2 = cur2->next;
            h2++;
        }
        ListNode* ret;
        int flag = 0;
        while (!s1.empty() || !s2.empty())
        {
            int a = 0, b = 0;
            if (!s1.empty())
            {
                a = s1.top()->val;
                s1.pop();
            }

            if (!s2.empty())
            {
                b = s2.top()->val;
                s2.pop();
            }
            int sum = a + b + flag;
            flag = sum / 10;
            sum %= 10;
            ListNode* newnode = new ListNode(sum);
            newnode->next = ret;
            ret = newnode;
        }
        if (flag)
        {
            ListNode* newnode = new ListNode(1);
            newnode->next = ret;
            ret = newnode;
        }
        return ret;

    }
};

int main()
{
    Solution s;
    vector<int> a({ 3,2,3,1,2,4,5,5,6 });

    int ret = s.findKthLargest(a, 4);
    cout << ret;
}
